//给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。 
//
// 示例 1: 
//
// 输入: s = "anagram", t = "nagaram"
//输出: true
// 
//
// 示例 2: 
//
// 输入: s = "rat", t = "car"
//输出: false 
//
// 说明: 
//你可以假设字符串只包含小写字母。 
//
// 进阶: 
//如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？ 
// Related Topics 排序 哈希表

package leetcode.editor.cn;

public class ValidAnagram {
    public static void main(String[] args) {
//        quickSort(array, 0, 4);
//        System.out.println(array);
        Solution solution = new ValidAnagram().new Solution();
        boolean b = solution.isAnagram("", null);
        System.out.println(b);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean isAnagram(String s, String t) {
            if (s == null && t == null) {
                return true;
            }
            if (s == null && t != null) {
                return false;
            }

            if (s != null && t == null) {
                return false;
            }

            if (s.length() != t.length()) {
                return false;
            }


            char[] charsOfLeft = s.toCharArray();
            char[] charsOfRight = t.toCharArray();

            quitckSort(charsOfLeft,0,charsOfLeft.length - 1);
            quitckSort(charsOfRight,0,charsOfRight.length - 1);

            for (int i = 0; i < charsOfLeft.length; i++) {
                if (charsOfLeft[i] != charsOfRight[i]) {
                    return false;
                }
            }

            return true;
        }

        private void quitckSort(char[] array, int leftBound,
                                int rightBound) {
            if (array.length < 1) {
                return;
            }
            if (leftBound >= rightBound) {
                return;
            }

            int i = leftBound;
            int j = rightBound;
            int pivot = array[leftBound];

            while (i < j) {
                int currentOfRight;
                while ((currentOfRight = array[j]) >= pivot && i < j) {
                    j--;
                }

                int currentOfLeft;
                while ((currentOfLeft = array[i]) <= pivot && i < j) {
                    i++;
                }

                if (i < j) {
                    array[i] = (char) currentOfRight;
                    array[j] = (char) currentOfLeft;
                }
            }

            // 交换 array[i/j] 与array[left]
            array[leftBound] = array[i];
            array[i] = (char) pivot;

            quitckSort(array, leftBound, i - 1);
            quitckSort(array, i + 1, rightBound);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}